package org.example.SolutionNew002;

import java.util.Comparator;
import java.util.PriorityQueue;

public class LinkedList12 {
    public static void main(String[] args) {
        LinkedList12 l = new LinkedList12();
        ListNode head1 = new ListNode(5);
        head1.next = new ListNode(-1);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(2);
        head1.next.next.next.next = new ListNode(1);
        ListNode res=l.sortList(head1);
        while(res!=null){
            System.out.println(res.val);
            res=res.next;
        }
    }

    public ListNode sortList1(ListNode head) {
        if (head == null || head.next == null)  return head;
        //可以用小根堆排序，用列表排序
        ListNode dummy=new ListNode(0);
        PriorityQueue<ListNode> pq=new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        ListNode cur=head;
        while(cur!=null){
            pq.add(cur);
            cur=cur.next;
        }
        ListNode temp=dummy;
        while(!pq.isEmpty()){
            ListNode now=pq.poll();
            now.next=temp.next;
            temp.next=now;
            temp=temp.next;
        }
        return dummy.next;
    }

    //归并排序
    public ListNode sortList2(ListNode head) {
        return sortList2(head,null);
    }

    public ListNode sortList2(ListNode head,ListNode tail){
        if(head==null||head==tail) return null;
        if(head.next==tail){
            head.next=null;
            return head;
        }
//        if(head.next.next==tail){
//            if(head.val>head.next.val){
//                ListNode newHead=head.next;
//                head.next=null;
//                newHead.next=head;
//                head=newHead;
//            }else{
//                head.next.next=null;
//            }
//            return head;
//        }
//
//        //正常
//        ListNode slow=head,fast=head;
//        while(fast.next!=tail && fast.next.next!=tail){
//            slow=slow.next;
//            fast=fast.next.next;
//        }
//        ListNode before=sortList(head,slow);
//        ListNode after=sortList(slow,tail);
        ListNode slow=head,fast=head;
        while(fast!=tail){
            slow=slow.next;
            fast=fast.next;
            if(fast!=tail){
                fast=fast.next;
            }
        }
        ListNode mid=slow;
        ListNode before=sortList2(head,mid);
        ListNode after=sortList2(mid,tail);
        return mergeTwoList(before,after);
    }

    public ListNode mergeTwoList(ListNode l1,ListNode l2){
        ListNode dummy=new ListNode(0);
        ListNode cur=dummy;
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                cur.next=l1;
                l1=l1.next;
            }else{
                cur.next=l2;
                l2=l2.next;
            }
            cur=cur.next;
        }
        ListNode temp= l1==null?l2:l1;
        cur.next= temp;
        return dummy.next;
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        int length=0;
        ListNode node=head;
        while(node!=null){
            length++;
            node=node.next;
        }
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        for(int subLength=1;subLength<length;subLength<<=1){
            ListNode prev=dummy,curr=dummy.next;
            while(curr!=null){
                ListNode head1=curr;
                for(int i=1;i<subLength&&curr.next!=null;i++){
                    curr=curr.next;
                }
                ListNode head2=curr.next;
                curr.next=null;
                curr=head2;

                for(int i=1;i<subLength&&curr!=null&&curr.next!=null;i++){
                    curr=curr.next;
                }
                ListNode next=null;
                if(curr!=null){
                    next=curr.next;
                    curr.next=null;
                }
                ListNode merged=mergeTwoList(head1,head2);
                prev.next=merged;
                while(prev.next!=null){
                    prev=prev.next;
                }
                curr=next;
            }
        }
        return dummy.next;
    }
}
